package Queue;

public class PriorityQueue implements IQueue {
    // 优先队列

    // 首节点
    private PriorityNode front;
    // 尾结点
    private PriorityNode rear;

    public PriorityQueue() {
        front = rear = null;
    }

    // 清空队列
    public void clear() {
        front = rear = null;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return front == null;
    }

    // 返回队列的长度
    public int length() {
        int i = 0;
        for(PriorityNode p=front; p!=null; p=p.next){
            i++;
        }
        return i;
    }

    // 读取首元素并且返回其值
    public Object peek() {
        if(isEmpty()){
            return null;
        }else {
            PriorityNode p = front;
            return p.data;
        }
    }

    // 入队
    public void offer(Object x, int priority) throws Exception {
        PriorityNode s = new PriorityNode(x, priority);
        // 如果队列非空
        if(!isEmpty()){
            PriorityNode p = front;
            PriorityNode q = front;
            while(p!=null && p.priority<=s.priority){
                // 通过优先级数来找到位置
                // 其中q代表目标存放的位置
                // 循环结束后  q.next == p
                q = p;
                p=p.next;
            }
            // 元素存储的位置的情况分开讨论
            if(p == null){
                // 在队尾
                // 修改前队尾结点指向当前节点
                // 在 另结尾节点为当前节点
                rear.next = s;
                rear = s;
            }else if(p==front){
                // 在队首
                // 把这个结点的下一个节点指向前首节点
                // 把当前节点换成首节点
                s.next = front;
                front = s;
            }else{
                // 队中
                // 前一个节点指向 s
                // 把 s 指向 后一个节点 整个链路完成
                q.next = s;
                s.next = p;
            }
        }else {
            rear = front = s;
        }


    }

    // 出队
    public Object poll() {
        if (isEmpty()){
            return null;
        }else {
            PriorityNode p = front;
            // 做判断 如果首节点与尾结点为同一个结点
            if(p==rear){
                // 尾结点同样置为空
                rear = null;
            }
            front = front.next;
            return p.data;
        }


    }

    // 展示队列中的所有元素
    public void display() {
        if(isEmpty()){
            System.out.println("没有元素");
        }else {
            for(PriorityNode p=front; p!=null; p=p.next){
                System.out.println(p.data+"  ");
            }
        }
    }

    public void offer(Object x) throws Exception {

    }
}
